package com.ainge.easystudy.binary;

import java.io.Serializable;
import java.util.Objects;

/**
 * 重复造轮子之通过写LRU来更深入理解HashMap
 *
 * @author: Ainge
 * @Time: 2021/9/18 23:43
 */
public class EasyLruHashMap<K, V> implements Serializable {
    /**
     * 数组
     */
    private Node<K, V>[] table;
    /**
     * 容量size
     */
    private int size;

    /**
     * 初始化时所允许的最大容量,2的16次方就够了。
     */
    static final int ALLOW_MAX_CAPACITY = 1 << 16;
    /**
     * 负载因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
     * 真正存储的元素个数限制，超过了按lru处理
     */
    int allowSize;

    /**
     * 最大容量，不进行扩容实现，用的时候，需要预估最大容量
     */
    int maxFixedTableSize;
    /**
     * 额外花费空间维护一个链表
     * 从 head --> node1 --> node2 --> tail
     * 越在前，说明越少被使用。当size > allowSize时，需要移除最年老的元素
     * 达到LRU效果
     */
    Node<K, V> eldest;

    public EasyLruHashMap(int maxFixedTableSize) {
        // 确保capacity为2的n次幂
        this.maxFixedTableSize = tableSizeFor(maxFixedTableSize);
        this.allowSize = (int) (this.maxFixedTableSize * DEFAULT_LOAD_FACTOR);
    }

    public V put(K key, V value) {
        // 像写业务代码一样写EasyHashMap
        if (table == null) {
            // 延迟初始化
            initTable();
        }
        int hash = hash(key);
        int n = maxFixedTableSize;
        int index = hash & (n - 1);
        // p元素
        Node<K, V> p = table[index];
        if (p == null) {
            // 该位置还没有元素，直接添加
            table[index] = new Node<>(hash, key, value);
            size++;
            // 每次都新建一个node节点副本
            addYoungestNode(new Node<>(hash, key, value));
            return null;
        }
        // 该位置已存在元素了，需要比较，key相同则覆盖，key不相同的话就尾插法
        if (Objects.equals(key, p.key)) {
            V oldValue = p.value;
            p.value = value;
            refreshNode(new Node<>(hash, key, value));
            return oldValue;
        }
        // 遍历链表，若无相同，则尾插入。
        for (; ; ) {
            Node<K, V> next = p.next;
            if (next == null) {
                p.next = new Node<>(hash, key, value);
                size++;
                addYoungestNode(new Node<>(hash, key, value));
                return null;
            }
            // next != null ,则需要比较
            if (Objects.equals(next.key, key)) {
                V oldValue = next.value;
                next.value = value;
                refreshNode(new Node<>(hash, key, value));
                return oldValue;
            }
            // 继续下一轮
            p = next;
        }
    }

    public V get(K key) {
        int hash = hash(key);
        int n = maxFixedTableSize;
        Node<K, V> firstNode = table[hash & n - 1];
        if (firstNode != null) {
            if (firstNode.hash == hash && Objects.equals(firstNode.key, key)) {
                refreshNode(new Node<>(hash, key, firstNode.value));
                return firstNode.value;
            }
            // 循环链表去获取
            Node<K, V> next = firstNode.next;
            while (next != null) {
                if (next.hash == hash && Objects.equals(next.key, key)) {
                    refreshNode(new Node<>(hash, key, next.value));
                    return next.value;
                }
                // 下一个
                next = next.next;
            }
        }
        return null;
    }

    public V remove(K key) {
        int hash = hash(key);
        int n = maxFixedTableSize;
        Node<K, V> firstNode = table[hash & n - 1];
        if (firstNode != null) {
            if (firstNode.hash == hash && Objects.equals(firstNode.key, key)) {
                Node<K, V> next = firstNode.next;
                table[hash & n - 1] = next;
                V value = firstNode.value;
                firstNode.next = null;
                --size;
                removeNode(firstNode.hash, firstNode.key);
                return value;
            }
            // 循环中的节点
            Node<K, V> next = firstNode.next;
            // 循环中节点的前节点
            Node<K, V> prev = firstNode;
            while (next != null) {
                if (next.hash == hash && Objects.equals(next.key, key)) {
                    // 匹配上了，断开该节点即可
                    prev.next = next.next;
                    V value = next.value;
                    next.next = null;
                    --size;
                    removeNode(next.hash, next.key);
                    return value;
                }
                prev = next;
                next = next.next;
            }
        }
        return null;
    }


    public int size() {
        return size;
    }

    private void initTable() {
        this.table = (Node<K, V>[]) new Node[maxFixedTableSize];
    }

    private int hash(Object key) {
        int h;
        // 当key ！= null，进行异或，使最终hash值具有高低位的特性（当table数组不大的时候，参与下标&运算的只有低位而已，n-1高位一般都是0）
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }


    private int tableSizeFor(int capacity) {
        // 预先减去1，预防当capacity刚好是2次幂的时候
        int n = capacity - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n <= 0) ? 1 : (n > ALLOW_MAX_CAPACITY) ? ALLOW_MAX_CAPACITY : n + 1;
    }

    private void addYoungestNode(Node<K, V> addNode) {
        if (eldest == null) {
            eldest = addNode;
            return;
        }
        // 检查是否超出容量，超过了要移除不活跃的元素，也就是eldest
        if (this.size > this.allowSize) {
            Node<K, V> eldestNode = getEldestNode();
            remove(eldestNode.key);
        }
        Node<K, V> tail = getTailNode();
        tail.next = addNode;
    }

    /**
     * 获取eldest链表的最后一个节点
     *
     * @return
     */
    private Node<K, V> getTailNode() {
        // TODO 优化，不应该每次都遍历获取，可以冗余在成员变量中去维护
        Node<K, V> firstNode = eldest;
        // 链表最后一个非空节点
        Node<K, V> tail = null;
        while (firstNode != null) {
            tail = firstNode;
            firstNode = firstNode.next;
        }
        return tail;
    }

    /**
     * 刷新节点，该节点被访问过，需要移动到尾节点
     *
     * @param node
     */
    private void refreshNode(Node<K, V> node) {
        Node<K, V> firstNode = this.eldest;
        Node<K, V> tailNode = getTailNode();
        if (tailNode.hash == node.hash && Objects.equals(node.key, tailNode.key)) {
            // 当前节点已经是最新
            return;
        }
        if (firstNode.hash == node.hash && Objects.equals(node.key, firstNode.key)) {
            this.eldest = firstNode.next;
            tailNode.next = node;
            firstNode.next = null;
            return;
        }
        Node<K, V> next = firstNode.next;
        Node<K, V> prev = firstNode;
        while (next != null) {
            if (next.hash == node.hash && Objects.equals(node.key, next.key)) {
                prev.next = next.next;
                tailNode.next = node;
                next.next = null;
                return;
            }
            prev = next;
            next = next.next;
        }
    }

    private Node<K, V> getEldestNode() {
        Node<K, V> firstNode = this.eldest;
        // 移除头节点
        return firstNode;
    }

    // 方便调试
    public void eldestNodePrint() {
        Node<K, V> eldestNode = getEldestNode();
        StringBuffer sb = new StringBuffer();
        while (eldestNode != null) {
            // 按最不活跃的顺序打印出所有node的值
            sb.append(eldestNode.value).append("_");
            eldestNode = eldestNode.next;
        }
        System.out.println(sb);
    }

    private void removeNode(int hash, K key) {
        Node<K, V> firstNode = this.eldest;
        if (firstNode.hash == hash && Objects.equals(firstNode.key, key)) {
            this.eldest = firstNode.next;
            firstNode.next = null;
            return;
        }
        Node<K, V> next = firstNode.next;
        Node<K, V> prev = firstNode;
        while (next != null) {
            if (next.hash == hash && Objects.equals(next.key, key)) {
                prev.next = next.next;
                next.next = null;
                return;
            }
            prev = next;
            next = next.next;
        }
    }

    private static class Node<K, V> {
        /**
         * 下一个节点
         */
        Node<K, V> next;
        /**
         * key
         */
        K key;
        /**
         * key.hashCode
         */
        final int hash;

        V value;

        Node(int hash, K key, V value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }


    public static void main(String[] args) {
        // 初始化固定8，那么8* 3/4 = 6，超过6个元素就会删除最少访问的那个
        EasyLruHashMap<Integer, String> map = new EasyLruHashMap<>(8);
        map.put(1, "1");
        map.put(2, "2");
        map.put(3, "3");
        map.put(4, "4");
        map.put(5, "5");
        map.put(6, "6");
        map.put(7, "7");
        // 1会被移除了
        System.out.println("get(1)=" + map.get(1));
        //打印 2_3_4_5_6_7_  7为最新
        map.eldestNodePrint();
        System.out.println("============");
        System.out.println("put(2,22），返回旧值=" + map.put(2, "22"));
        //打印 3_4_5_6_7_22_  22为最新
        map.eldestNodePrint();
        System.out.println("============");
        System.out.println("remove(3），返回旧值=" + map.remove(3));
        System.out.println("get(6)=" + map.get(6));
        map.get(7);
        //打印 4_5_22_6_7_  7为最新
        map.eldestNodePrint();
        // 再加入两个元素，检查4是否被移除
        map.put(8, "8");
        map.put(9, "9");
        System.out.println("get(4)=" + map.get(4));
        map.eldestNodePrint();
        System.out.println("============");

        // hash冲突严重的测试
        EasyLruHashMap<SameHashCodeObject, String> sameHashCodeObject = new EasyLruHashMap<>(8);

        sameHashCodeObject.put(new SameHashCodeObject(1), "1");
        sameHashCodeObject.put(new SameHashCodeObject(2), "2");
        sameHashCodeObject.put(new SameHashCodeObject(3), "3");
        sameHashCodeObject.put(new SameHashCodeObject(4), "4");

        sameHashCodeObject.put(new SameHashCodeObject(30), "30");
        sameHashCodeObject.put(new SameHashCodeObject(30), "40");
        sameHashCodeObject.put(new SameHashCodeObject(40), "40");
        sameHashCodeObject.put(new SameHashCodeObject(50), "50");
        sameHashCodeObject.eldestNodePrint();
        Node<SameHashCodeObject, String>[] table = sameHashCodeObject.table;
        for (int i = 0; i < table.length; i++) {
            if (table[i] != null) {
                System.out.println("table size = 8，not null table index=" + i);
            }
        }
    }

    static class SameHashCodeObject implements Serializable {
        private int id;

        public SameHashCodeObject(int id) {
            this.id = id;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            SameHashCodeObject that = (SameHashCodeObject) o;
            return id == that.id;
        }

        @Override
        public int hashCode() {
            // 错误的示范：
            if (id < 10) {
                return 1;
            }
            return 2;
        }
    }
}
